package com.mccken.practice.data_structure.data_01;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-27 14:24
 **/
public class DoubleList_01 {
	
	// 头虚节点
	private Node_01 head;
	// 尾虚节点
	private Node_01 tail;
	
	// 链表元素数量
	private int size;
	
	public DoubleList_01(){
		// 初始化双向链表数据
		head = new Node_01(0,0);
		tail = new Node_01(0,0);
		head.next = tail;
		tail.prev = head;
		size = 0;
	}
	
	// 在链表尾部添加节点x，时间复杂度为O(0)
	public void addLast(Node_01 x) {
		x.prev = tail.prev;
		x.next = tail;
		tail.prev.next = x;
		tail.next = x;
		size++;
	}
	
	// 删除链表中的x节点 （一定存在）
	// 此时是双向链表，并且目标接节点一定存在，时间复杂度为O(1)
	public void remove(Node_01 x) {
		x.prev.next = x.next;
		x.next.prev = x.prev;
		size--;
	}
	
	// 删除链表中的第一个节点，并且返回该节点，时间复杂度为O(1)
	public Node_01 removeFirst() {
		if (head.next == tail) {
			return null;
		}
		
		Node_01 first = head.next;
		remove(first);
		return first;
	}
	
	public int size() {
		return size;
	}
}
